package algorithm.dp;

public class 拼接最大数N {
    /*
     * 给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m +
     * n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
     * 
     * 求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
     * 
     * 说明: 请尽可能地优化你算法的时间和空间复杂度。
     * 
     * 示例 1:
     * 
     * 输入: nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 输出: [9, 8, 6,
     * 5, 3] 示例 2:
     * 
     * 输入: nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 输出: [6, 7, 6, 0, 4] 示例 3:
     * 
     * 输入: nums1 = [3, 9] nums2 = [8, 9] k = 3 输出: [9, 8, 9]
     * 
     * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/create-maximum-number
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        /*
         * 假设从nums1[0:i-1]与nums2[0:j-1]中选取了m-1位组建了最大数max[0:m-1],那么则比较nums1[i]
         * 与nums2[j],选取更大的数组成最大数max[0:m] 1、最大数的比较，转换成str则能够不限制长度比较 2、
         * 
         * 77 / 102 个通过测试用例 超时
         */
        int len1 = nums1.length;
        int len2 = nums2.length;
        String[][][] dp = new String[len1 + 5][len2 + 5][k + 5];
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                dp[i][j][0] = "";
            }
        }
        String temp = null;
        String tmep0 = null;
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                for (int m = 1; m <= i + j && m <= k; m++) {
                    if (dp[i][j][m] != null) {
                        continue;
                    }
                    if (i >= 1 && dp[i - 1][j][m - 1] != null) {
                        temp = dp[i - 1][j][m - 1] + nums1[i - 1];
                        dp[i][j][m] = max(dp[i - 1][j][m], temp);
                    }
                    if (j >= 1 && dp[i][j - 1][m - 1] != null) {
                        temp = dp[i][j - 1][m - 1] + nums2[j - 1];
                        dp[i][j][m] = max(dp[i][j - 1][m], max(dp[i][j][m], temp));
                    }
                }
            }
        }
        String max = "";
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                max = max(dp[i][j][k], max);
            }
        }
        int[] res = new int[k];
        int index = 0;
        for (char ch : max.toCharArray()) {
            res[index++] = ch - '0';
        }
        return res;
    }

    String max(String str1, String str2) {
        if (str1 == null) {
            return str2;
        }
        if (str2 == null) {
            return str1;
        }
        if (str1.compareTo(str2) > 0) {
            return str1;
        } else {
            return str2;
        }
    }

    public static void main(String[] args) {
        拼接最大数N run = new 拼接最大数N();
        int[] nums1 = { 3, 4, 6, 5 };
        int[] nums2 = { 9, 1, 2, 5, 8, 3 };
        int k = 5;
        int[] nums3 = { 1, 5, 8, 1, 4, 0, 8, 5, 0, 7, 0, 5, 7, 6, 0, 5, 5, 2, 4, 3, 6, 4, 6, 6, 3, 8, 1, 1, 3, 1, 3, 5,
                4, 3, 9, 5, 0, 3, 8, 1, 4, 9, 8, 8, 3, 4, 6, 2, 5, 4, 1, 1, 4, 6, 5, 2, 3, 6, 3, 5, 4, 3, 0, 7, 2, 5, 1,
                5, 3, 3, 8, 2, 2, 7, 6, 7, 5, 9, 1, 2 };
        int[] nums4 = { 7, 8, 5, 8, 0, 1, 1, 6, 1, 7, 6, 9, 6, 6, 0, 8, 5, 8, 6, 3, 4, 0, 4, 6, 7, 8, 7, 7, 7, 5, 7, 2,
                5, 2, 1, 9, 5, 9, 3, 7, 3, 9, 9, 3, 1, 4, 3, 3, 9, 7, 1, 4, 4, 1, 4, 0, 2, 3, 1, 3, 2, 0, 2, 4, 0, 9, 2,
                0, 1, 3, 9, 1, 2, 2, 6, 6, 9, 3, 6, 0 };
        k = 80;
        System.out.println(run.maxNumber(nums1, nums2, 5));
    }
}
